package com.jlhlyby.num;

/**
 * 【把一个数分解成任意几个数之和】
 * 思想，动态规划，将大问题拆分成小问题，
 * 首先将对数n的拆分转换成 m和对n-m的拆分
 * 如果4 转换成1和3的拆分
 * 3转换成1和2的拆分
 * 但是为了防止【1，2，1】和【1，1，2】这种重复的出现，要进行一个有序处理
 * 优先拆分出最小的数，后面的数必须大于等于前一个数
 * 如4拆分成 【1，1，1，1】【1，1，2】【1，3】【2，2】
 * 参考链接：https://blog.csdn.net/qq_45502554/article/details/102786353
 * 单注意链接中实现没有排除自己，我代码中有注释
 */
public class NumberSplit {
    static int[] arr;
    static int num = 5;

    public static void main(String[] args) {
        arr = new int[num];
        doSplit(num, 1, 0);
    }

    /**
     * 递归实现
     *
     * @param remain 拆分后剩余的需要再次拆分的数
     * @param pre    前一个数
     * @param index  当前是第几个数了
     */
    public static void doSplit(int remain, int pre, int index) {
        //如果剩余的没了就可以输出了
        if (remain <= 0) {
            for (int i = 0; i < index; i++) {
                System.out.print(arr[i]+",");
            }
            System.out.println();
        } else {
            //i从和前一个数一样开始逐渐增大,
            for (int i = pre; i <= remain; i++) {
                //排除自己本身如 4=【4】
                if (index == 0 && i == remain){
                    return;
                }
                arr[index] = i;
                //求出剩余的数继续拆分
                doSplit(remain - i, i, index + 1);
            }
        }

    }
}
